

#include<iostream>
#include<vector>

using namespace std;


int main()
{
	int N, V; cin >> N >> V;


	vector<int>v(N);
	vector<int>w(N);
	vector<vector<int>>dp(N + 1, vector<int>(V + 1));


	for (int i = 0; i < N; i++)cin >> v[i] >> w[i];

	//第一行全部初始化为0
	//直接从第二行开始填表
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= V; j++)
		{
			dp[i][j] = dp[i - 1][j];//不装
			if (j >= v[i - 1])//装
				dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i - 1]] + w[i - 1]);
		}
	}

	cout << "dp表为:" << "\n";
	for (auto row : dp)
	{
		for (auto x : row)
		{
			cout << x << " " ;
		}
		cout << "\n";
	}


	cout << "Ret: "<<dp[N][V] << endl;
	return 0;
}


